package day07;

import java.util.Stack;

/**
 * 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,
 * 5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：
 * 这两个序列的长度是相等的）
 * 
 * @author Administrator
 *
 */
public class Test03 {

	public static void main(String[] args) {
		int[] arr = { 1, 2, 3, 4, 5 };
		// int[] arr1 = { 4, 5, 3, 2, 1 };
		int[] arr1 = { 4, 3, 5, 1, 2 };
		System.out.println(IsPopOrder(arr, arr1));
	}

	public static boolean IsPopOrder(int[] pushA, int[] popA) {
		Stack<Integer> stack = new Stack<Integer>();
		int index = 0;
		if (pushA == null || popA == null || pushA.length == 0 || popA.length == 0 || pushA.length != popA.length) {
			return false;
		}
		for (int i = 0; i < pushA.length; i++) {
			if (stack.isEmpty()) {
				stack.push(pushA[i]);
			} else if (stack.peek() != popA[index]) {
				stack.push(pushA[i]);
			} else {
				stack.pop();
				index++;
				stack.push(pushA[i]);
			}
		}
		while (!stack.isEmpty()) {
			Integer pop = stack.pop();
			int result = pop.compareTo(popA[index++]);
			if (result != 0) {
				return false;
			}
		}
		return true;
	}
}
